#!/usr/bin/php
<?PHP

define("MAX", 10);

function arrayInit(array & $arr, int $max = 0,
                        bool $rand = TRUE, int $rand_max = 9999999)
{
    for ($i = 0, $m = $max == 0 ? sizeof($arr): $max; $i < $m; ++$i) {
        if ($rand)
            $arr[$i] = mt_rand(0, $rand_max);
        else {
            printf("请输入整型数(%d): ", $i);
            fscanf(STDIN, "%d", $arr[$i]);
        }
    }
}

function arrayOut(array & $arr, string $prompt = "")
{
    echo "$prompt";
    foreach ($arr as $val) {
        echo "$val ";
    }
    echo "\n";
}

$a = array();
arrayInit($a, 10, TRUE, 100);
arrayOut($a, "init: ");

// sort($a);
// arrayOut($a, "sort: ");

function hash_index($val, $max): int
{
    return $val % $max;
}

$hash = array();
foreach ($a as $v)
{
    $hash[hash_index($v, MAX)][] = $v;
}

foreach($hash as $k => $r)
{
    printf("[%d]: ", $k);

    foreach ($r as $v)
    {
        echo "$v ";
    }
    printf("\n");
}

while (TRUE)
{
    printf("请输入查找数: ");
    fscanf(STDIN, "%d", $n);

    if ($n == -1)
        break;

    // 顺序查找
    /*
     * foreach ($a as $v)
     * {
     *     if ($v == $n)
     *         printf("查找结果为 %d\n", $v);
     * }
     */

    // 二分查找
    /*
     * $l = 0;
     * $h = count($a);
     * while ($l <= $h)
     * {
     *     $m = (int)(($l + $h) / 2);
     *     if ($n > $a[$m])
     *         $l = $m + 1;
     *     else if ($n < $a[$m])
     *         $h = $m - 1;
     *     else
     *     {
     *         printf("查找结果为 %d\n", $n);
     *         break;
     *     }
     * }
     */

    //哈希查找
    // printf("查找结果为 %d\n", $hash[hash_index($n, 100)]);
    $index = hash_index($n, MAX);
    foreach ($hash[$index] as $val)
    {
        if ($val == $n)
            printf("查找结果为 %d\n", $n);
    }
}
